#include "stdio.h"
#include "stdlib.h"

typedef struct BSTNode{
	int key;
	BSTNode *lchild,*rchild;
}*BSTree,BSTNode;

BSTNode *BSTSerch(BSTree T,int key);
BSTNode *BSTRSerch(BSTree T,int key);
bool BSTRInsert(BSTree &T,int key);
void createBST(BSTree &T,int str[],int n);
void printBST(BSTree T);

int main(){
	int a[]={3,2,4,1,5};
	BSTree T;
	createBST(T,a,5);
	printBST(T);
	
	return 0;
}

BSTNode *BSTSerch(BSTree T,int key){
	while(T!=NULL&&key!=T->key)
		if(key<T->key)
			T=T->lchild;
		else
			T=T->rchild;
	
	return T;
}
BSTNode *BSTRSerch(BSTree T,int key){
	if(T!=NULL)
		return NULL;
	if(key==T->key)
		return T;
	else if(key < T->key)
		return BSTRSerch(T->lchild,key);
	else 
		return BSTRSerch(T->rchild,key);
}
bool BSTRInsert(BSTree &T,int key){
	if(T==NULL){
		T = (BSTree)malloc(sizeof(BSTNode));
		T->key=key;
		T->lchild=T->rchild=NULL;
		return true;
	}
	else if(key == T->key)
		return false;
	else if(key < T->key)
		return BSTRInsert(T->lchild,key);
	else 
		return BSTRInsert(T->rchild,key);
}
void createBST(BSTree &T,int str[],int n){
	T=NULL;
	int i=0;
	while(i<n)
		BSTRInsert(T,str[i++]);
		
}
void printBST(BSTree T){
	
	if(T!=NULL){
		printBST(T->lchild);
		printf("%d",T->key);
		printBST(T->rchild);
	}
	
}